In an online system providing search results based on user queries, often the objects being searched are evaluated under a variety of factors in order to produce search results that meet the user's needs as well as the needs of the online system. Query rewriting is one aspect of such a search engine. Query rewriting functions to adjust the terms used in a search to match the available search results, and in some systems query rewriting is primarily responsible for establishing the set of results that are retrieved in response to a user's search query. Systems and methods described herein relate to improved query rewriting.